import java.math.BigInteger;
import java.util.regex.Pattern;

public class RadixConvertor {//进制转换器

	private final static char[] charTable = {//包含的转义字符放在charTable最后面
			'0','1','2','3','4','5','6','7','8','9',
			'A','B','C','D','E','F','G','H','I','J',
			'K','L','M','N','O','P','Q','R','S','T',
			'U','V','W','X','Y','Z','a','b','c','d',
			'e','f','g','h','i','j','k','l','m','n',
			'o','p','q','r','s','t','u','v','w','x',
			'y','z','`','~','!','@','#','$','%','^',
			'&',42,40,41,'-','_','=',43,91,123,
			']','}','|',';',':',',','<','.','>','/',
			63,' ','\'','\"',92,'\t','\n'
			//为了避免IDEA报错,42为*,40为(,41为),43为+,91为[,123为{,63为?,92为\
	};

	public final static int MAXRADIX = charTable.length;//允许的最大进制数为charTable的表长

	private final static String VALID_REGEX = generateRegex();//合法的数字字符串的正则表达式，即charTable元素的自由组合，null也合法
	private final static String ZERO_ONLY_REGEX = charTable[0]+"+";//匹配仅由值为0的字符组成的正则表达式

	private final static int DIVISIONLIMIT = 6;//一次循环中除法次数限制,越小算法越快(不可小于2),若问题规模太大而这个值太小会StackOverflow
	private final static int MULTIPLYLIMIT = 6;//一次循环中乘法次数限制,不可小于2

	private static double k;

	/*
	以下是public方法
	 */
	
	public static String toDecimal(String numString,int RADIXbefore){//转十进制

		if(!Pattern.matches(VALID_REGEX,numString))//numString必须符号正则表达式REGEX
			throw new IllegalArgumentException("parameter numString is illegal");
		if(RADIXbefore<2)//输入的RADIXbefore不能小于2，不能大于MAXRADIX
			throw new IllegalArgumentException("parameter RADIX cannot less than 2");
		if(RADIXbefore>MAXRADIX)
			throw new IllegalArgumentException("parameter RADIX cannot bigger than " + MAXRADIX);
		if(RADIXbefore == 10 || numString == null)//当RADIXbefore为10或者数字字符串为null，则不必进行进制转换
			return numString;
		if(numString.matches(ZERO_ONLY_REGEX))//当numString仅由值为0的字符组成，返回值为0的字符
			return charTable[0]+"";

		numString = deleteZeroAtHead(numString);//将首部多余的值为0的字符去除
		
		final BigInteger bi = toDecimalDivideAndConquer(numString,RADIXbefore);

		final String str = bi.toString();//这个方法花去了不少时间

		//k = Math.log(10)/Math.log(2);

		//final String str = convertDivideAndConquer(bi,0,10).toString();

		return str;
		
	}

	public static String convert(String numString,int RADIXbefore,int RADIXafter){//任意进制互转

		if(!Pattern.matches(VALID_REGEX,numString))//numString必须符号正则表达式REGEX
			throw new IllegalArgumentException("parameter numString is illegal");
		if(RADIXbefore<2||RADIXafter<2)//输入的RADIXbefore和RADIXafter不能小于2，不能大于MAXRADIX
			throw new IllegalArgumentException("RADIX cannot less than 2");
		if(RADIXbefore>MAXRADIX||RADIXafter>MAXRADIX)
			throw new IllegalArgumentException("RADIX cannot bigger than " + MAXRADIX);
		if(RADIXbefore == RADIXafter || numString == null)//当RADIXbefore与RADIXafter相等或者数字字符串为null，则不必进行进制转换
			return numString;
		if(numString.matches(ZERO_ONLY_REGEX))//当numString仅由值为0的字符组成，返回值为0的字符
			return charTable[0]+"";

		numString = deleteZeroAtHead(numString);//将首部多余的值为0的字符去除

		final BigInteger decimalNum = toDecimalDivideAndConquer(numString,RADIXbefore);
		//BigInteger是10进制运算，故先将numString转换为10进制以进一步计算
		//当RADIXbefore为10时，该方法也比直接new BigInteger(numString)要更快

		k = Math.log(RADIXafter)/Math.log(2);

		StringBuilder sb = convertDivideAndConquer(decimalNum,0,RADIXafter);

		return deleteZeroAtHead(sb.toString());

	}

	/*
	以下是private方法
	 */

	private static StringBuilder convertDivideAndConquer(BigInteger var,int lastExp,int targetRadix){
		//分治法
		//BigInteger var.bitlength() = Math.ceil(log var / log 2 + 1)

		BigInteger radix;
		BigInteger quotient;
		BigInteger remainder;
		BigInteger[] temp;

		final double divideTimes = var.bitLength()/k;

		int exp = 1;

		if(divideTimes>DIVISIONLIMIT)
			exp = (int)(divideTimes/DIVISIONLIMIT)+1;

		final StringBuilder sb = new StringBuilder();

		radix = BigInteger.valueOf(targetRadix).pow(exp);//为了让除法执行次数减少到limit,将radix变为其exp次方

		do {

			temp = var.divideAndRemainder(radix);
			quotient = temp[0];
			remainder = temp[1];
			var = quotient;

			final StringBuilder unit = remainder.bitLength()/k>DIVISIONLIMIT?
					convertDivideAndConquer(remainder,exp,targetRadix):getRemainderSequence(remainder,targetRadix);

			for(int i=unit.length();i<exp;i++)
				unit.append('0');

			sb.append(unit);

		} while (var.compareTo(BigInteger.ZERO) != 0);

		if(lastExp==0)
			return sb.reverse();
		else{
			return setCorrectLength(sb,lastExp);
		}

	}

	private static StringBuilder getRemainderSequence(BigInteger var,int targetRadix){//除基取余法

		StringBuilder sb = new StringBuilder();

		if(k>var.bitLength()) {
			return sb.append(decode(var.intValue()));
		}

		BigInteger[] temp;
		BigInteger quotient;
		BigInteger remainder;
		final BigInteger radix = BigInteger.valueOf(targetRadix);

		do{

			temp = var.divideAndRemainder(radix);
			quotient = temp[0];
			remainder = temp[1];
			var = quotient;

			sb.append(decode(remainder.intValue()));

		} while (var.compareTo(BigInteger.ZERO) != 0);

		return sb;

	}

	private static BigInteger toDecimalDivideAndConquer(String numString,int radixBefore){

		numString = deleteZeroAtHead(numString);

		final int len = numString.length();
		int multiplyTimes = len-1;

		int exp = multiplyTimes>MULTIPLYLIMIT?len/MULTIPLYLIMIT:1;

		if(exp==1)
			return toDecimal_unit(numString,radixBefore);

		int remainder = len%exp;
		int loop = (len-remainder)/exp;

		StringBuilder sb = new StringBuilder();
		if(remainder!=0){
			loop++;
			for(int i=0;i<exp-remainder;i++)
				sb.append('0');
		}
		sb.append(numString);

		final BigInteger multiplier = BigInteger.valueOf(radixBefore).pow(exp);
		BigInteger addend;

		BigInteger bi = toDecimalDivideAndConquer(sb.substring(0,exp),radixBefore);

		for(int i=1;i<loop;i++){//秦九韶算法

			addend = toDecimalDivideAndConquer(sb.substring(i*exp,(i+1)*exp),radixBefore);
			bi = bi.multiply(multiplier).add(addend);

		}

		return bi;

	}
	
	private static BigInteger toDecimal_unit(String numString,int RADIXbefore){//将numString从RADIXbefore转换为10进制
		
		final BigInteger biRADIXbefore = BigInteger.valueOf(RADIXbefore);
		
		final int length = numString.length();
		int p;

		BigInteger bi = BigInteger.valueOf(encode(numString.charAt(0)));
		
		for(int i=1;i<length;i++){//秦九韶算法

			p = encode(numString.charAt(i));
			bi = bi.multiply(biRADIXbefore).add(BigInteger.valueOf(p));

		}
		
		return bi;
		
	}

	private static String generateRegex(){//根据charTable生成合法数字字符串的正则表达式

		StringBuilder sb = new StringBuilder();

		for(int i=0;i<MAXRADIX;i++)
			sb.append(charTable[i]);

		return "["+sb+"]*";

	}

	private static StringBuilder setCorrectLength(StringBuilder sb,int len){//将sb设置为正确的长度,长度偏大则去除前面多余的0，偏小则给前面添加0

		final int l = sb.length();
		final int diff = l - len;
		if(diff==0)
			return sb;
		else if(diff>0){
			return new StringBuilder(sb.substring(0,l - diff));
		}else{
			StringBuilder prefix = new StringBuilder();
			prefix.append(sb);
			for(int i=diff;i!=0;i++)
				prefix.append('0');
			return prefix;
		}

	}

	private static String deleteZeroAtHead(String str) {//删除str头部多余的0,若str完全由0组成,返回"0"
		int surplusZero = 0;//多余的0的数量
		final int len = str.length();
		for (int i = 0;i<len&&str.charAt(i)==charTable[0];i++)
			surplusZero++;
		if(surplusZero==len)
			surplusZero--;
		return str.substring(surplusZero);
	}

	private static int encode(char c){//编码，将字符变为对应的数值

		int index = -1;
		
		for(int i=0;i<MAXRADIX;i++){
			
			if(charTable[i] == c){
				
				index = i;
				break;
				
			}
			
		}

		return index;
		
	}
	
	private static char decode(int index){//解码，将数值变为对应的字符
		
		return charTable[index];
		
	}
}
